#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/18 22:16
# @USER    : Shengji He
# @File    : GroupAnagrams.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from collections import defaultdict
from typing import List


class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        """
        Given an array of strings, group anagrams together.

        Example:
            Input: ["eat", "tea", "tan", "ate", "nat", "bat"],

            Output:

            [
              ["ate","eat","tea"],  \n
              ["nat","tan"],        \n
              ["bat"]               \n
            ]

        Note:
            - All inputs will be in lowercase.
            = The order of your output does not matter.

        :param strs:
        :return:
        """
        ans_dict = defaultdict(list)
        for element in strs:
            key = ''.join(sorted(element))
            # key = tuple(sorted(s))
            ans_dict[key].append(element)
        return list(ans_dict.values())


if __name__ == '__main__':
    S = Solution()
    strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
    print(S.groupAnagrams(strs))
    print('done')
